#include<cstdio>

int main(){
    int n;
    int dp[10001][100001]; 
    while (scanf("%d", &n) && n){

    }
}